\documentclass[]{report}
\usepackage[frenchb]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{algorithmic}
\usepackage{titlesec} 
\titleformat{\chapter}[hang]{\bf\huge}{\thechapter}{2pc}{} 
\setcounter{tocdepth}{1}
\begin{document}
\title{\Huge{Projet CAA \\ Couverture par sommets}
\vspace{10mm}
\vspace{15mm}
\normalsize{\\Chargé de TD : Alexandre ZVONKINE\\
Responsable de l'UE : Philippe DUCHON}
}
\author{Tempier Grégory \and Mothe Alexandre \and Milian Paul}
\maketitle
\newpage
\tableofcontents
\newpage
\chapter{Présentation du sujet}
\section{La couverture par sommets}
Le but de ce projet est de pouvoir trouver une couverture minimale pour des graphes, qu'ils soient sous forme d'arbres, bipartis ou quelconques. On dit qu'un graphe est couvert lorsque chacune des arêtes a au moins une des extrémités qui est reliée à un sommet couvrant, et cette couverture est minimale lorsqu'on est certain qu'il n'existe pas de couverture ayant moins de sommet.\\

Dans ce projet, nous allons étudier les algorithmes qui génèrent ces graphes et qui calculent les couvertures de plusieurs façons : soit en obtenant une couverture minimale, soit en l'approchant, au profit de la complexité.\\

Le problème de la couverture par sommets est NP-complet: on ne peut pas trouver d'algorithme s'exécutant en temps polynomial pour des graphes quelconques. Nous implémenterons donc des algorithmes ayant un temps polynomial pour des classes particulières de graphes, approchés sinon.

\chapter{Génération d'arbres}
\section{Présentation de l'algorithme}
Cet algorithme prend pour seul paramètre un nombre de sommets, et génère un arbre aléatoirement. Pour ce faire nous générons un premier sommet, en tenant à jour un nombre de sommets restants à placer. Pour chaque tour de boucle, on regarde s'il nous reste des fils à placer pour ce sommet, auquel cas on les ajoute, sinon on passe au sommet suivant. En ajoutant au graphe que des arêtes vers des sommets n'ayant pas été placés, nous nous assurons de ne pas avoir de cycles, et donc d'avoir un arbre.
\section{Estimation de la complexité}
L'algorithme fait autant de tours de boucle while que d'arêtes à placer, qui correspond directement au nombre de sommets vu que le graphe est un arbre. Les fonctions addVertex() et addEdge() ayant une complexité en $O(1)$, la complexité totale de l'algorithme est en $O(n)$.
\section{Résultats d'expérimentation}


\chapter{Génération de graphes}
\section{Présentation de l'algorithme}
Pour générer des graphes quelconques, nous prenons en paramètre le nombre de sommets total et la probabilité d'avoir une arête entre deux sommets. Nous ajoutons les sommets un à un, puis parcourons la liste des sommets déjà placés et pour chacun on teste si une arête doit exister entre ce sommet et le dernier sommet placé.
\section{Estimation de la complexité}
Nous avons une première boucle while, qui parcourt tous les sommets du graphe, et à chaque fois on parcourt les sommets déjà placés dans une boucle for. La complexité de cet algorithme est donc en $O(n^{2})$.


\chapter{Génération de graphes bipartis}
\section{Présentation de l'algorithme}
Pour ce type de graphes, nous choisissons d'abord un nombre aléatoire entre 1 et le nombre de sommets total, qui représente notre nombre de sommets noirs. Tous les sommets sont ensuite ajoutés au graphe. Nous parcourons ensuite la liste des sommets noirs, et pour chacun on parcourt la liste des sommets blancs afin de tester si une arête existe entre eux.
\section{Estimation de la complexité}
Tout d'abord nous faisons un premier parcours pour ajouter les sommets noirs ensuite de même pour les sommets blancs. Une fois les sommets ajoutés au graphe, nous faisons un parcours des sommets noirs, et à chaque itération nous refaisons un parcours des sommets blancs. La complexité de cet algorithme est donc $O(n^{2})$.


\chapter{Génération de graphes à petite couverture}
\section{Présentation de l'algorithme}
Pour générer ce type de graphes, nous reprenons l'idée des graphes bipartis. Dans ce cas là, nous créons une liste de N sommets couvrants prédéfinis, puis pour chacun d'entre eux nous parcourons la liste des sommets, en faisant des liens avec les autres sommets, même ceux appartenant à la liste des couvrants, selon la probabilité passée en paramètre.
\section{Estimation de la complexité}
Notre générateur fait une première boucle pour créer les couvrants, puis en fait un deuxième parcours,et pour chacun de ces parcours, on regarde chaque sommet déjà existant, ce qui nous donne une complexité en $O(n^{2})$.


\chapter{Résultats d'expérimentation sur la génération de graphes}
Voici un test de performances comparatifs entre nos algorithmes de résolution de graphes, obtenu avec gnuplot. Le nombre de sommets du graphe se trouve en abscisse, et le temps pris pour générer le graphe est en ordonnée. Les courbes obtenues ne sont pas parfaitement lisses; ceci est probablement dû à un défaut de cache lorsque le nombre de sommets devient trop grand. Pour la génération de graphe à petite couverture, la couverture demandée est nbsommet/10. Tree n'est pas visible sur le graphique car il s’exécute trop rapidement.
\begin{center}
\input{../VertexCover/src/graph1}
\end{center}


\chapter{Algorithme glouton pour graphes quelconques}
\section{Présentation de l'algorithme}
Pour cette méthode de résolution, nous créons tout d'abord une copie de notre graphe afin de pouvoir la modifier. A chaque tour de la boucle principale, nous regardons si notre copie dispose encore d'arêtes, et si c'est le cas, on cherche le sommet ayant le plus grand degré, afin de le supprimer avec toutes les arêtes qui lui sont reliées et on le rajoute à la liste des couvrants. Cette méthode ne donne pas un résultat optimal, mais permet d'avoir une bonne approximation pour un temps de calcul court.
\section{Estimation de la complexité}
Nous utilisons dans cet algorithme les fonctions
hasNoEdge: parcourt simplement les sommets et est donc de complexité $O(n)$. 
getNbVertex : récupération d'une donnée donc $O(1)$.
numEdge : récupération d'une donnée donc $O(1)$.
delVertex : simple boucle for qui utilise delEdge, lui même en $O(n)$; la complexité est donc en $O(n^{2})$.
L'enchaînement de ces fonctions dans notre boucle principale fait que la complexité théorique de l'algorithme est $O(n^{2})$, seulement vu que nous détruisons les arêtes, la complexité totale diminue à chaque tour.


\chapter{Algorithme optimal pour les arbres}
\section{Présentation de l'algorithme}
Pour récupérer la couverture, on commence par faire un parcours en profondeur. Si on arrive sur une feuille, on la marque comme non couvrante, et si on arrive sur un nœud, alors on regarde tous ses fils. Si l'un d'entre eux n'est pas couvrant, alors on marque ce sommet comme étant couvrant.
\section{Estimation de la complexité}
Nous nous sommes arrangés pour ne pas avoir à reparcourir la liste des fils pour savoir si l'un d'entre eux est couvrant, donc la complexité globale de l'algorithme se résume à celle d'un parcours en profondeur classique, soit en O(V+E) avec V le nombre de sommets et E le nombre d'arêtes.
\section{Résultats d'expérimentation}


\chapter{Algorithme 2-approché pour les graphes quelconques (parcours d'arbre}
\section{Présentation de l'algorithme}
Pour cet algorithme, nous transformons un graphe quelconque en arbre, avant de lui appliquer l'algorithme optimal sur les arbres. Cette solution est limitée dans le fait que pour que la transformation en arbre fonctionne, le graphe passé en paramètre doit être connexe. Une solution à ce problème pourrait être de diviser le graphe de base en plusieurs sous graphes connexes, puis d'appliquer la transformation en arbres dessus.
\section{Estimation de la complexité}
Pour transformer un graphe en arbre, nous faisons appel à a fonction makeTree. Cette fonction parcourt juste une première fois la liste des sommets avant d’appeler makeTreeAux. C'est donc une fonction en $O(n)$.
Pour makeTreeAux, à première vue c'est une fonction récursive pour parcourir tout le graphe, doublée d'une boucle for pour parcourir les voisins d'un sommet. Et donc la complexité théorique est en $O(n^{2})$. Seulement, notre tableau ''available'' limite grandement le nombre d'appel, et la fonction tend donc vers $O(n)$. Ce que l'on vérifie expérimentalement dans notre partie tests.


\chapter{Algorithme 2-approché pour les graphes quelconques (élimination du voisinage}
\section{Présentation de l'algorithme}
Normalement, pour cet algorithme, nous devons choisir une arête au hasard dans le graphe. Notre système de représentation n'étant pas adapté, nous avons choisi de prendre le premier sommet ayant au moins un voisin, le premier de ses voisins, et choisissons l'arête entre eux. Pour chaque arête ainsi choisie, on note ces deux sommets comme couvrants, et on les supprime du graphe.
\section{Estimation de la complexité}
Nous faisons un simple parcours de graphe, mais les fonctions appelées ont également une complexité en $O(n)$. La complexité totale de notre algorithme est donc en $O(n^{2})$, ce que l'on vérifie expérimentalement.


\chapter{Résultats d'expérimentation sur la résolution}
Nous comparons ici nos différents algorithmes sur la résolution des graphes. Ici, les tests ont été réduits à des graphes de 1000 sommets, afin d'avoir des temps de calcul acceptables. Les courbes du graphe optimal pour les arbres et du biparti2approché n'apparaissent pas car leur temps de calcul est trop rapide. De plus, nous n'avons pas pu faire de tests concluants sur l'algorithme 2 approché par les arbres car notre génération de graphes ne garanti pas d'avoir un graphe connexe.
\begin{center}
\input{../VertexCover/src/results/graph2}
\end{center}

\include{optibiparti}

\include{minisat}

\end{document}
